1044. Longest Duplicate Substring - LeetCode Solution

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        power = 2**63 - 1
        def rabin(mid):
            chash = 0
            for i in range(mid):
                chash = (chash * 26 + nums[i]) % power
            hashes = {chash}
            position = -1
            max_pow = pow(26, mid, power)
            for i in range(mid, len(S)):
                chash = (26*chash-nums[i-mid]*max_pow + nums[i]) % power
                if chash in hashes:
                    position = i + 1 - mid
                hashes.add(chash)
            return position


        low, high = 0, len(S)-1
        end = 0
        start = 0
        nums = [ord(c)-ord('a') for c in S]
        while low <= high:
            mid = (low+high) // 2
            position = rabin(mid)
            if position == -1:  # no matching strings found
                high = mid - 1
            else:
                start = position
                low = mid + 1
        return S[start:start+low-1]